﻿#define PROCSPEC

#include "LineFinder.h"

//  解一行，返回修改格子数
int LineFinder::procALine(Cell* wl, int wlen, Flags& flags)
{
	workLine = wl;
    workLineLen = wlen;
	workFlags = &flags;
	stepCount = 0;

#ifdef PROCSPEC
    //  特殊处理头尾，增加解出率，可以不要。理论上应该可以加速。
    //  如有已解出的 flag, 则分段处理
    for (int i = 0; i < flags.len;)
        if (flags.f[i].ok()) ++i;
        else
        {
            int j;
            for (j = i + 1; j < flags.len && !flags.f[j].ok(); ++j)
				;
            if (!procFirstLast({i == 0 ? 0 : flags.f[i - 1].nextpos() + 1, j < flags.len ? flags.f[j].pos - 2 : wlen - 1}, flags.f[i], flags.f[j - 1]))     //  返回 true 则原位再次尝试，否则从下个区段继续
                i = j + 1;
        }
//    if (stepCount > 0)          //  有解出的格子就不递归，下次仍处理此行/列（flags.needProc不变，还是true）,本意是加速，结果更慢
//        return stepCount;
#endif

    procExhaust({0, wlen - 1}, {0, flags.len - 1});
    flags.needProc = false;         // 完成递归则不需要再次递归
	return stepCount;
}

bool LineFinder::procSpec(const Posi& wp, Flag& flag)
{
    // 处理 wp 空间内肯定有 flag 的情况
    // 按最大可能填充 Yes
    Posi yeslr = {wp.end - flag.n + 1, wp.st + flag.n - 1};
    fillPos(yeslr, Cell::Yes);
    // 向两边扩展可能已经存在的 Yes
    yeslr.st = rightSeekN({wp.st, yeslr.st - 1}, Cell::Yes);
    yeslr.end = leftSeekN({yeslr.end + 1, wp.end}, Cell::Yes);
    // 填充可能的区间前后可能的 NO
    fillPos({wp.st, yeslr.end - 1 - flag.n}, Cell::No);
    fillPos({yeslr.st + 1 + flag.n, wp.end}, Cell::No);
    // 填充后计数连续的 Yes 是否等于 flag, 等于说明已确定
    if (yeslr.len() == flag.n + 2)
	{
        flag.pos = yeslr.st + 1;
        fillPosNoEx(yeslr.st);
        fillPosNoEx(yeslr.end);
        return true;
	}
    return false;
}

bool LineFinder::procFirstLast(Posi wp, Flag& flagFirst, Flag& flagLast)
{
    // 特殊处理头尾flag
    // 跳过左边的No
    wp.st = leftSeekN(wp, Cell::No);
    int staddN = wp.st + flagFirst.n;
    // 左边第一个No的左边空间小于flag,则空间填充No
    if (int ln = leftSeek({wp.st + 1, staddN - 1}, Cell::No); ln < staddN)      //  c++17 if 初始化
	{
		fillPos({wp.st, ln - 1}, Cell::No);
        return true;
	}
    // 右边处理原理同上
    wp.end = rightSeekN(wp, Cell::No);
    int endsubN = wp.end - flagLast.n;
    if (int rn = rightSeek({endsubN + 1, wp.end - 1}, Cell::No); rn > endsubN)
	{
		fillPos({rn + 1, wp.end}, Cell::No);
        return true;
	}

    // 处理左右靠边的Yes（Yes到边的距离小于flag）
    bool res = false;
    if (int ly = leftSeek({wp.st, staddN}, Cell::Yes); ly <= staddN)
        res = procSpec({wp.st, leftSeek({ly + 1, std::min(wp.end, ly + flagFirst.n - 1)}, Cell::No) - 1}, flagFirst);
    if (int ry = rightSeek({endsubN, wp.end}, Cell::Yes ); ry >= endsubN)
        res |= procSpec({rightSeek({std::max(wp.st, ry - flagLast.n + 1), ry - 1}, Cell::No) + 1, wp.end}, flagLast);

    return res;
}

// -------------------------------- 穷举法 --------------------------------------
// 思路：穷举一行的每一种符合规则的放置办法
// 如果所有方案中一格都yes则此格确定为yes；
// 反之如果所有方案中一格都no则此格确定为no；其他情况表示此格不确定。
// 返回值表示是否需要再次递归
int LineFinder::procExhaust(const Posi& wp, const Posi& fp)
{
	exhaNum = 0;
	for (int i = wp.st; i <= wp.end; ++i) countLine[i] = 0;

	if (fp.len() > 0)
	{
		recuFp = fp;
		validWlst = wp.st;
        recuWlend = wp.end;
        recuWlRightYes = rightSeek(wp, Cell::Yes);
        // 计算第n个flag的最右可能位置（考虑空隙），递归时使用
        for (int p = recuWlend + 1, i = fp.end; i >= fp.st; --i)
        {
            p -= workFlags->f[i].n;
            mostRight[i] = p--;
        }

        if (int res = recursion(wp.st, fp.st)) return res;      //  超过最大递归或解不出，返回
		if (exhaNum == 0) throw Err::CantFit;		   //  一个解都没有，说明题目有问题

		// 设置已解决的flag
		for (int j = fp.st; j <= fp.end; ++j)
			if (sign[j] >= 0) workFlags->f[j].pos = sign[j];
	}

	// 根据穷举的结果设置 yes or no
	for (int i = wp.st; i <= wp.end; ++i)
		if (countLine[i] == 0)
			fillPos(i, Cell::No);
		else if (countLine[i] == exhaNum)
			fillPos(i, Cell::Yes);
	return 0;
}

// 放置一个flag,判断合理性，递归放置后续flag
// 输入参数 curWp 当前格子，curFp 当前要放置的flag；终点是全局量 recuWp 和 recuFp
// 返回值 0: 已成功尝试所有可能; 1: 不能确定任何结果; 2: 超过最大递归次数或
int LineFinder::recursion(int curWp, int curFp)
{
	// 本次要放置的flag值
	int curN = workFlags->f[curFp].n;
	// 确定最右尝试的位置：最末一格减去之后flag的最小格数和 与 最左的 yes 中的小值
    int tmpEnd = std::min(mostRight[curFp], leftSeek({curWp, recuWlend}, Cell::Yes));
	// 确定最左尝试的位置：如果是最后一个flag，则必须用到已的有yes，从可能的位置尝试
	if (curFp == recuFp.end && curWp + curN <= recuWlRightYes)
		curWp = recuWlRightYes - curN + 1;

	// 从可能的最左到最右格子逐个判断是否合规则
	for (; curWp <= tmpEnd; ++curWp)
	{
		// 检测本次放置是否合规则
		// 本次放置的区间之后一格不应该是Yes，不满足尝试下个位置
		int nextWp = curWp + curN;
        if (workLine[nextWp] == Cell::Yes && nextWp <= recuWlend) continue;
		// 本次放置的区间之内不应该有No，如有从No后继续尝试
        if (int m = rightSeek({curWp, nextWp - 1}, Cell::No); m >= curWp)
        {
            curWp = m;
            continue;
        }

		// 此位置合理，记录位置
		recuPos[curFp] = curWp;
        if (curFp == recuFp.end)
		{
			// 是最后一个flag，说明已取得一个合理解
			// 超过最大递归数，停止
			if (++exhaNum >= maxExha) return 2;
			// 处理此解
            for (int k = recuFp.st; k <= recuFp.end; ++k)
			{
                int p = recuPos[k];
                // 如果是第一个解，记录位置；之后的解比较位置，位置不同记录-1，所有解位置都一样，说明此flag位置确定
                if (int& sk = sign[k]; exhaNum == 1)
                    sk = p;
                else
                    if (sk != p) sk = -1;
                // 此解用到的格子记数+1
                for (int n = workFlags->f[k].n; n > 0; --n) ++countLine[p++];
            }
            //  全部格子已经确定无用（计数不为0和Exhanum，则无法确定此格yes or no），则退出（加速用，可以不要）
            auto between = [en = exhaNum](unsigned int a) { return a > 0 && a < en; };    //  c++17 初始化捕获
            //auto between = [](unsigned int a, unsigned int en) static { return a > 0 && a < en; };         //  c++23 static lambda
            while (between(countLine[validWlst]))
                if (++validWlst > recuWlend) return 1;
        }
		else
			// 从下一个位置递归下一个flag
			if (int res = recursion(nextWp + 1, curFp + 1)) return res;
	}
	return 0;
}

void Line::fillPos(int pos, Cell c)
{
    Cell& w = workLine[pos];
    if (w == Cell::Unknow)
	{
        w = c;
		stepCount++;
//        if (chgFlags) chgFlags[pos].changed = true;       此功能移到Map中实现
	}
    else
        if (w != c) throw Err::GridRewrite;
}

int Line::leftSeek(const Posi& wp, Cell c) const
{
	int i = wp.st;
    for (; workLine[i] != c && i <= wp.end; ++i)
        ;
	return i;
}

int Line::leftSeekN(const Posi& wp, Cell c) const
{
    int i = wp.st;
    for (; workLine[i] == c && i <= wp.end; ++i)
        ;
    return i;
}

int Line::rightSeek(const Posi& wp, Cell c) const
{
	int i = wp.end;
    for (; workLine[i] != c && i >= wp.st; --i)
        ;
	return i;
}

int Line::rightSeekN(const Posi& wp, Cell c) const
{
    int i = wp.end;
    for (; workLine[i] == c && i >= wp.st; --i)
        ;
    return i;
}
